package org.example.y24.m11;

import java.util.Random;

public class QuickSort {
    //快速排序
    public int[] sortArray(int[] nums) {
        quickSort(nums, 0, nums.length - 1);
        return nums;
    }

    public static void quickSort(int[] arr, int left, int right) {
        if (left < right) {
            int pos = sort(arr, left, right);

            quickSort(arr, left, pos - 1);
            quickSort(arr, pos + 1, right);
        }
    }

    private static int sort(int[] arr, int left, int right) {
        int pivot = arr[right];
        int i = (left - 1);
        for (int j = left; j < right; j++) {
            if (arr[j] <= pivot) {
                i++;

                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }
        int temp = arr[i + 1];
        arr[i + 1] = arr[right];
        arr[right] = temp;
        return i + 1;
    }


}
